package day2_linkedlist.mylink.double_linkedlist;

/**
 * 12-07更新双向链表代码
 */
public class DoubleLinkedList {
    private static class Node {
        private int val;
        private Node prev;
        private Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(Node prev,int val, Node next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    private int size;
    private Node head;
    private Node tail;

    public void addFirst(int val) {
        Node node = new Node(null,val,head);
        // 当前链表为空
        if (head == null) {
            tail = node;
        }else {
            head.prev = node;
        }
        head = node;
        size ++;
    }

    public void addLast(int val) {
        Node node = new Node(tail,val,null);
        if (tail == null) {
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size ++;
    }

    public void addIndex(int index,int val) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        else if (index == 0) addFirst(val);
        else if (index == size) addLast(val);
        else  {
            // 原先index - 1位置节点
            Node prev = node(index - 1);
            Node newNode = new Node(prev,val,prev.next);
            prev.next.prev = newNode;
            prev.next = newNode;
            size ++;
        }
    }

    // 返回index位置节点
    private Node node(int index) {
        Node node = null;
        if (index < size << 1) {
            node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }else {
            node = tail;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    public void removeIndex(int index) {
        if (index < 0 || index >= size) {
            System.err.println("remove index illegal!");
            return;
        }
        Node node = node(index);
        unlink(node);
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    public void removeValueOnce(int val) {
        for (Node x = head;x != null;x = x.next) {
            if (x.val == val) {
                unlink(x);
                break;
            }
        }
    }

    public void removeAllValue(int val) {
        for (Node x = head;x != null;) {
            if (x.val == val) {
                Node next = x.next;
                unlink(x);
                x = next;
            }else {
                x = x.next;
            }
        }
    }

    // 将node节点从原链表中删除
    private void unlink(Node node) {
        // 分治思想
        Node prev = node.prev;
        Node next = node.next;
        if (prev == null) {
            head = next;
        }else {
            node.prev = null;
            prev.next = next;
        }
        if (next == null) {
            tail = prev;
        }else {
            next.prev = prev;
            node.next = null;
        }
        size --;
    }

    @Override
    public String toString() {
        StringBuilder sb =  new StringBuilder();
        Node node = head;
        while (node != null) {
            sb.append(node.val).append("->");
            node = node.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

}
